package com.zhugang.week13.recursion;

/**
 * @program algorithms
 * @description: fib
 * @author: chanzhugang
 * @create: 2022/11/17 09:40
 */
public class Fib {

    /**
     * 剑指offer 10-I 斐波那契数列
     * https://leetcode.cn/problems/fei-bo-na-qi-shu-lie-lcof/
     * 没用备忘录：时间复杂度是指数级，画递归树理解，是一个歪把子树
     *
     * @param n
     * @return
     */
    int[] mem;
    int mod = 1000000007;

    public int fib(int n) {
        /**
         * 递归求解, 备忘录解决重复计算，套一个壳
         * 答案需要取模 1000000007
         */
        mem = new int[n + 1];
        return fib_(n);
    }

    private int fib_(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        // 大量剪枝效果
        if (mem[n] != 0) return mem[n];
        mem[n] = (fib(n - 1) + fib_(n - 1)) % mod;
        return mem[n];
    }
}